Dynamic flow completion from limited observation data is a common problem that arises in many fields such as crowd flow estimation, air flow sensing, and weather and ocean current prediction.
For example, regarding crowd flow estimation, the segmentation of motion flows within dense crowds of pedestrians in videos is an essential tool in crowd safety and crowd control applications. Videos of crowded scenes can exhibit complex crowd behaviors even under normal situations. For example, crowd flows in large congested areas, such as train stations, can initially appear chaotic. However, is often the case that low dimensional dynamical structures exist in the flow that is desirable to identify and segment from unstructured flows. Moreover, the automatic segmentation of independent crowd flows aids in the monitoring and prediction of hazardous situations in crowded environments.
Of particular interest is the detection and estimation of crowd flows using motion information extracted from the videos. Motion vectors can be determined using optical flow estimation applied to texture, that is pixel intensities, in videos, or the motion vectors can be extracted directly from a bitstream. The bitstream can encoded using any of the well known coding standards, e.g., MPEG, H.264, HEVC, etc.
Considering pedestrians in a crowded scene as particles in a flow, the motion vectors of a video frame correspond to observations of the velocities of particles at a time instance in the flow. Processing motion vectors, instead of the video texture, protects the privacy of individuals observed in surveillance videos.
U.S. Pat. No. 8,773,536 discloses a method for detecting independent motion in a surveillance video. The method constructs a linear system from macroblocks of the video by comparing texture gradients with motion vector. Independent flows are detected when the motion is flagged as a statistical outlier relative to the linear system.
Macroscopic Model for Pedestrian Flows
The macroscopic model for crowd flow considers the crowd as a flowing continuum and describes the average behavior of pedestrians. The model parameters are the density of the crowd ρ, and the horizontal and vertical velocities (u,v) at each point in the grid Ω. Macroscopic models for crowd flow are similar to models of fluid dynamics and are governed by the following hypothyses: (1) the speed of pedestrians at each point is determined only by the density of the crowd around that point; (2) Pedestrians have a common goal (potential); (3) Pedestrians want to minimize the estimated travel time, simultaneously avoiding the large density areas.
These hypotheses can be translated into the following PDE
                    {                                                                                                                                                ∂                        t                                            ⁢                      ρ                                        +                                                                  ∂                        x                                            ⁢                                              (                                                  ρ                          ⁢                                                                                                          ⁢                          u                                                )                                                              +                                                                  ∂                        y                                            ⁢                                              (                                                  ρ                          ⁢                                                                                                          ⁢                          v                                                )                                                                              =                  0                                ,                                                                                                                                                    ρ                      ⁢                                                                        ∂                          t                                                ⁢                        u                                                              +                                          ρ                      ⁡                                              (                                                                              u                            ⁢                                                                                          ∂                                x                                                            ⁢                              u                                                                                +                                                      v                            ⁢                                                                                          ∂                                y                                                            ⁢                              u                                                                                                      )                                                              +                                                                  K                        2                                            ⁢                                                                        ∂                          x                                                ⁢                        ρ                                            ⁢                                                                                          ⁢                                              v                                                  x                          0                                                                                                      =                                                            ρA                      1                                        ⁡                                          [                                              ρ                        ,                                                  v                          →                                                                    ]                                                                      ,                                                                                                                                                    ρ                      ⁢                                                                        ∂                          t                                                ⁢                        v                                                              +                                          ρ                      ⁡                                              (                                                                              u                            ⁢                                                                                          ∂                                x                                                            ⁢                              v                                                                                +                                                      v                            ⁢                                                                                          ∂                                y                                                            ⁢                              v                                                                                                      )                                                              +                                                                  K                        2                                            ⁢                                                                        ∂                          y                                                ⁢                        ρ                                            ⁢                                                                                          ⁢                                              v                                                  y                          0                                                                                                      =                                                            ρA                      2                                        ⁡                                          [                                              ρ                        ,                                                  v                          →                                                                    ]                                                                      ,                                                                        (        1        )            where ρ(x,y) is the density, u(x,y) is the horizontal velocity, v(x,y) are respectively the horizontal and vertical velocities at all point (x,y)∈Ω, andA1[ρ,{right arrow over (v)}]=α{circumflex over (u)}(ρ)(x0−x),A2[ρ,{right arrow over (v)}]=α{circumflex over (v)}(ρ)(y0−y)encode the goal of the pedestrians with (x0,y0) being the target position and (x,y) the current positions. α and K are model parameters. The functions û(ρ)=uo(1−ρ/ρo) and {circumflex over (v)}(ρ)=vo(1−ρ/ρo) obey the Greenshield's model which couples the magnitude of the velocity to the density. This allows to drive the dynamical system using either the velocity or the density alone.
Koopman and Dynamic Mode Decomposition
The Koopman Operator
Let (M,n,F) be a discrete time dynamical system, where M⊆RN is the state space, n∈Z is the time parameter and F:M→M is the system evolution operator. The Koopman operator K is defined on the space of functions F, where F={ϕ|ϕ:M→C}, as follows:Kϕ=ϕ∘F.  (2)
The Koopman operator is linear and infinite dimensional, and it admits eigenvalues and eigenfunctions. For vector valued observables g:M→RNis o, the Koopman operator also admits Koopman modes. The Koopman operator specifies a new discrete time dynamical system on the function space (F,n,K). Let φk(x), 1≤k≤K be the top K eigenfunctions of K. Without loss of generality, let the system variable be x∈M and assume that the function g(x)=x. Then, shows that
      g    ⁡          (      x      )        =      x    =                  ∑                  k          =          1                K            ⁢                          ⁢                        ξ          k                ⁢                              φ            k                    ⁡                      (            x            )                              and the future state F(x) can be estimated as
                                          F            ⁡                          (              x              )                                =                                                    (                Kg                )                            ⁢                              (                x                )                                      =                                                            ∑                                      k                    =                    1                                    K                                ⁢                                                                  ⁢                                                                            ξ                      k                                        ⁡                                          (                                              K                        ⁢                                                                                                  ⁢                                                  φ                          k                                                                    )                                                        ⁢                                      (                    x                    )                                                              =                                                ∑                                      k                    =                    1                                    K                                ⁢                                                                  ⁢                                                      λ                    k                                    ⁢                                      ξ                    k                                    ⁢                                                            φ                      k                                        ⁡                                          (                      x                      )                                                                                                          ,                            (        3        )            where ξk and λk are the Koopman modes and Koopman eigenvalues.
Kernel Dynamic Mode Decomposition
Williams et al. proposed the Kernel DMD (KDMD) algorithm as a low complexity method for approximating the Koopman operator. Let ƒ:M×M→R be a kernel function, and define the following data matricesĜij=ƒ(xi,xj),Âij=ƒ(yi,xi),  (4)where xi and yj are column vectors of the data sets X and Y. A rank-r truncated singular value decomposition of the symmetric matrix Ĝ results in the singular vector matrix Q and the singular value matrix Σ. The KDMD operator {circumflex over (K)} is then computed using{circumflex over (K)}=(Σ†QT)Â(QΣ†).  (5)
An eigenvalue decomposition of {circumflex over (K)} results in the eigenvector matrix {circumflex over (V)} and eigenvalue matrix Λ. It was shown in that Λ approximates the Koopman eigenvalues. Moreover, the Koopman eigenfunctions are approximated by the matrix Φ=VTΣTQT. Since every data point xi=Σkλkξkφk, the Koopman modes are approximated by the matrix Ξ=XΦ†=QΣ{circumflex over (V)}†, where X=[x1 . . . xT].
For every new data point x*, the corresponding prediction y*≈F(x*) can be approximated using KDMD by first estimating the eigenfunction(x*)=Φ[ƒ(x*,x1),ƒ(x*,x2), . . . ,ƒ(x*,xT)]T,  (6)and using the Koopman prediction relation
                    {                                                                                                                        x                      *                                        ≈                                          Ξ                      ⁢                                                                                          ⁢                                              (                                                  x                          *                                                )                                                                              ,                                                                                                                          y                    *                                    ≈                                      ΞΛ                    ⁢                                                                                  ⁢                                          (                                              x                        *                                            )                                                                                                    .                                    (        7        )            
Accordingly, there is a need for a data anonymization method that can minimize or avoid the usage of the actual state of the device producing the data.